import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/13 9:09
 * @description list可以在O(1)时间内完成获取随机元素操作，但是无法在O(1)时间内判断元素是否存在，因此不能在O(1)时间复杂度内完成插入和删除操作
 * 改进见2
 */
public class RandomizedSet {
    List<Integer> list;
    public RandomizedSet() {
        list = new ArrayList<>();
    }

    public boolean insert(int val) {
        if (!list.contains(val)) {
            // contains时间复杂度为O(N)
            list.add(val);
            return true;
        }
        return false;
    }

    public boolean remove(int val) {
            if (list.contains(val)) {
                list.remove((Object) val);
                return true;
            }
            return false;
    }

    public int getRandom() {
        Random random = new Random();
        int k = random.nextInt(list.size());
        return list.get(k);
    }

    public static void main(String[] args) {
        RandomizedSet randomizedSet = new RandomizedSet();
        randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
        randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
        randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
        randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
        randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
        randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
        randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
    }
}
